// 文件名：multiset_sliding_window_median.cpp
// 目的：在数据流的滑动窗口中实时维护中位数，使用两个 std::multiset（双堆思想）。
// 模型：
//   - left_：存放窗口中较小的一半元素，按升序排列；我们用其最大值（rbegin）代表左堆顶；
//   - right_：存放窗口中较大的一半元素，按升序排列；我们用其最小值（begin）代表右堆顶；
// 不变式：
//   - size(left_) == size(right_) 或 size(left_) == size(right_) + 1；
//   - 所有 left_ 中元素 <= 所有 right_ 中元素；
// 插入：
//   - 新元素落到 left_ 或 right_，然后 balance() 调整两边规模与边界；
// 删除：
//   - 在 left_ 或 right_ 中查找并擦除该值（multiset 支持重复值），随后 balance()；
// 查询中位数：
//   - 若两边等大：中位数为 (max(left_) + min(right_)) / 2；
//   - 否则（left_ 多一个）：中位数为 max(left_)；
// 复杂度：
//   - insert/erase：O(log W)，W 为窗口大小；median：O(1)。
// 注意：
//   - multiset 允许存重复值，适合多次出现同一元素的窗口；
//   - balance() 通过移动边界元素保持不变式成立。

#include <iostream>
#include <set>
#include <vector>

class SlidingMedian {
public:
    // 插入一个元素到窗口
    void insert(int x) {
        if (left_.empty() || x <= *left_.rbegin()) {
            left_.insert(x);   // 落在左半部分
        } else {
            right_.insert(x);  // 落在右半部分
        }
        balance();
    }

    // 从窗口中删除一个元素（若存在多个，仅删一个）
    void erase(int x) {
        auto it = left_.find(x);
        if (it != left_.end()) {
            left_.erase(it);
        } else {
            it = right_.find(x);
            if (it != right_.end()) right_.erase(it);
        }
        balance();
    }

    // 返回当前窗口的中位数
    double median() const {
        if (left_.size() == right_.size()) {
            // 平均两个堆顶
            return (*left_.rbegin() + *right_.begin()) / 2.0;
        }
        // 左边多一个时，取左堆顶
        return static_cast<double>(*left_.rbegin());
    }

private:
    // 维持不变式：|left_| == |right_| 或 |left_| == |right_| + 1
    void balance() {
        if (left_.size() > right_.size() + 1) {
            // 左边多了：把左堆顶移到右边
            right_.insert(*left_.rbegin());
            left_.erase(std::prev(left_.end()));
        } else if (right_.size() > left_.size()) {
            // 右边多了：把右堆顶移到左边
            left_.insert(*right_.begin());
            right_.erase(right_.begin());
        }
    }

    std::multiset<int> left_;   // 左半部分（最大堆效果：取 rbegin）
    std::multiset<int> right_;  // 右半部分（最小堆效果：取 begin）
};

int main() {
    std::vector<int> stream = {5, 2, 7, 3, 9, 1, 4, 6};
    const std::size_t window = 4;

    SlidingMedian median;
    for (std::size_t i = 0; i < stream.size(); ++i) {
        median.insert(stream[i]);                   // 加入新样本
        if (i >= window) {                         // 窗口外的旧样本剔除
            median.erase(stream[i - window]);
        }
        if (i + 1 >= window) {                     // 窗口已满，输出中位数
            std::cout << "Window [" << i - window + 1 << ", " << i << "] median = "
                      << median.median() << '\n';
        }
    }
    return 0;
}